import java.util.Arrays;

public class PriorityQueue {
    int[] arr ;
    int size ;

    public PriorityQueue() {
    }

    public PriorityQueue(int[] arr, int size) {
        this.arr = arr;
        this.size = size;
    }

    //创建大根堆
    //创建小根堆只需要反转符号即可
    //时间复杂度O（n）;通过错位相减，求得树的高度再通过树的节点个数求得时间复杂度
    public  int[]  bigQueue(int[] arr ,int size){
        for(int parent = (size - 2) / 2;parent >= 0 ; parent--) {
        siftDown(parent, size);
        }
        return arr;
    }
    private void siftDown(int parent,int size){
        int child = parent * 2 + 1;
        while(child < size) {
            if(child + 1 < size && arr[child] < arr[child + 1]) {
                child++;
            }
            if(arr[child] > arr[parent] ) {
                swap(arr,child, parent);
                parent = child;
                child = parent * 2 + 1;
            }else{
                break;
            }

        }
    }
    private void swap(int[] arr, int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    @Override
    public String toString() {
        return "PriorityQueue{" +
                "arr=" + Arrays.toString(arr) +
                '}';
    }
    //删除元素
    public int poll() {
        //删除第一个元素：
        //将第一个元素和最后一个元素互换位置；
        //然后将size--;
        int top = arr[0];
        arr[0] = arr[size - 1];
        size--;
        siftDown(0,size);
        return top;
    }
    private void ifFull(){
        if(size == arr.length) {
            arr = Arrays.copyOf(arr,20);
        }
    }
    //向上调整，时间复杂度高于向下调整
    //时间复杂度O(n+logN);
    private void sifUp(int val){
        if(size == arr.length) {
            ifFull();
        }
        size++;
        arr[size - 1] = val;
        int child = size - 1;
        int parent = (child - 1)/2;
        while(child != 0 && arr[child] > arr[parent]){
                swap(arr , child ,parent);
                child = parent;
                parent = (child - 1) / 2;
            }


    }
    public void push(int val){
        sifUp(val);
    }
    //堆排序
    //从小到大：建立大根堆
    public void queueSort(){
        int end = size - 1;
        while(end > 0) {
            swap(arr,0,end);
            siftDown(0,--end);
        }
    }
}
